package Leetcode第二期;

import java.util.*;

/**
 * @author : K k
 * @date : 10:25 2020/9/17
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1：
 *
 * 输入：candidates = [2,3,6,7], target = 7,
 * 所求解集为：
 * [
 *   [7],
 *   [2,2,3]
 * ]
 * 示例 2：
 *
 * 输入：candidates = [2,3,5], target = 8,
 * 所求解集为：
 * [
 *   [2,2,2,2],
 *   [2,3,3],
 *   [3,5]
 * ]
 */
public class 组合总和_39 {
    private List<List<Integer>> res;
    private Deque<Integer> queue=new ArrayDeque<>();

    //思路： 回溯+剪枝，剪枝是让循环从index开始 保证前面的元素不会重复出现
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res=new ArrayList<List<Integer>>();
        int len=candidates.length;
        if (len == 0) {
            return res;
        }
        dfsSolver(candidates,0,len,target);
        return res;
    }

    private void dfsSolver(int[] candidates ,int index,int len, int target) {
        if (target==0){
            res.add(new ArrayList<>(queue));
            return;
        }else if (target<0){
            return;
        }

        for (int i=index;i<len;i++){
            /*if (!queue.isEmpty()&&candidates[i]<queue.getLast()){
                continue;
            }*/
            queue.addLast(candidates[i]);
            dfsSolver(candidates,i,len,target-candidates[i]);
            queue.removeLast();
        }
    }

    public static void main(String[] args) {
        组合总和_39 x=new 组合总和_39();
        System.out.println(x.combinationSum(new int[]{2, 3, 6, 7}, 8));
    }
}
